package gee

import "strings"

type node struct {
	pattern	string // 待匹配路由，例如 /p/:lang
	part	string    // 路由中的一部分，例如 :lang
	children []*node  // 子节点
	isWild	bool    // 是否精确匹配，part含有:或*时为true
}

// matchChild 匹配第一个part符合的节点
func (n *node) matchChild(part string) *node {
	for _, child := range n.children {
		if child.part == part || child.isWild {
			return child
		}
	}
	return nil
}

// matchChildren 匹配所有part符合的节点
func (n *node) matchChildren(part string) []*node {
	nodes := make([]*node, 0)
	for _, child := range n.children {
		if child.part == part || child.isWild {
			nodes = append(nodes, child)
		}
	}
	return nodes
}

// insert 插入一个路由
func (n *node) insert(pattern string, parts []string, height int) {
	// 叶节点存储整个pattern
	if len(parts) == height {
		n.pattern = pattern
		return
	}
	// 得到本层的路径字段
	part := parts[height]
	// 匹配一下节点
	child := n.matchChild(part)
	// 匹配失败就创建一个
	if child == nil {
		child = &node{
			part: part,
			isWild: part[0] == ':' || part[0] == '*',
		}
		n.children = append(n.children, child)
	}
	// 将子节点插入剩余部分的路由
	child.insert(pattern, parts, height + 1)
}

// search 搜索一个路由
func (n *node) search(parts []string, height int) *node {
	// 找到最后一个层或模糊条件时，判断当前节点为叶节点，返回遍历搜索结果
	if len(parts) == height || strings.HasPrefix(n.part, "*") {
		if n.pattern == "" {
			return nil
		}
		return n
	}
	// 得到下一节点part
	part := parts[height]
	// 找到符合的所有子节点
	children := n.matchChildren(part)
	// BFS遍历一下
	for _, child := range children {
		result := child.search(parts, height + 1)
		if result != nil {
			return result
		}
	}
	// 没遍历到，返回nil
	return nil
}